package com.hanxiaozhang.no10leetcode.array;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给一个未排序的整数数组，找到其中最长的连续元素个数，要求算法时间复杂度为O(n)
 * <p>
 * 实例:
 * 输入: [100, 4, 200, 1, 3, 2]
 * 输出: 4
 * 解释: 最长的连续元素序列是[1，2，3，4]。因此其长度为4。
 *
 * @author hanxinghua
 * @create 2024/1/29
 * @since 1.0.0
 */
public class No128LongestConsecutiveSequence {


    public static void main(String[] args) {


        int[] arr = {100, 4, 200, 1, 3, 2};

        System.out.println(method1(arr));
        System.out.println(method2(arr));

    }


    public static int method2(int[] nums) {
        HashMap<Integer, Integer> resMap = new HashMap<>();
        int res = 0;
        for (Integer i : nums) {
            if (!resMap.containsKey(i)) {
                int left = resMap.get(i - 1) == null ? 0 : resMap.get(i - 1);
                int right = resMap.get(i + 1) == null ? 0 : resMap.get(i + 1);
                int sum = left + right + 1;
                res = Math.max(res, sum);
                resMap.put(i, sum);
                resMap.put(i - left, sum);
                resMap.put(i + right, sum);
            } else {
                continue;
            }
        }
        return res;
    }


    /**
     * 方法1
     * <p>
     * 不符合要求的解题思路
     *
     * @param arr
     * @return
     */
    private static int method1(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j] ^ arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                }
            }
        }

        int maxLength = 0, count = 1;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i; j < arr.length - 1; j++) {
                if (arr[j + 1] - arr[j] == 1) {
                    count++;
                }
            }
            maxLength = Math.max(maxLength, count);
            count = 1;
        }
        return maxLength;
    }
}
